package packet1;

import java.util.*;

public class Main1 {
    public static boolean get(int n,int m){
        int t=0;
        while(m>0){
            t=n%m;
            n=m;
            m=t;
        }
        if(n==1)return true;
        return false;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[] a=new int[n+1];
        int max=-1;
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            max=max>a[i]? max:a[i];
        }
        for(int i=0;i<m;i++){
            int res=0;
            int l=sc.nextInt();
            int r=sc.nextInt();
            int k=sc.nextInt();
            int[] b=new int[max+1];
            for(int j=l;j<=r;j++){
                b[a[j]]+=1;
            }
            for(int j=0;j<b.length;j++){
                if(b[j]==0)continue;
                if(get(b[j],k))res++;
            }
            System.out.println(res);
        }
    }
}
